package MelbourneMap;

import java.lang.reflect.Array;

/**
 * Array implementation of generic Binary Heap. Contains two private
 * instance variables one for the array itself and the other for the 
 * size of the array. It also contains two constructors, one with a 
 * default array length of 100 and the other allowing the user to set 
 * the length. There are five public methods to perform Binary Heap 
 * operations and two private methods to aid in their implementation.
 * 	
 * @author David Zappia, 7183216
 *
 * @param <T>		the type to be stored in the PriorityQueue
 */
public class PriorityQueue<T extends Comparable<? super T>> 
{
	/**
	 * Special exception class to handle PriorityQueue
	 * exceptions.
	 * 
	 * @author David Zappia, 7183216
	 *
	 */
	public static class MyException extends RuntimeException
	{
		
		/**
		 * Class constructor.
		 */
		public MyException()
		{
			super();
		}
		
		/**
		 * Creates a new exception with the specified message
		 * 
		 * @param message		the message to be displayed with the exception
		 */
		public MyException(String message)
		{
			super(message);
		}
	}
	
	private T[] elements = (T[]) new Comparable[0]; // The array of comparable items stored in the heap.
	private int size; // The current size of the heap.
	
	/**
	 * Class constructor creates an array with a size of 100.
	 */
	public PriorityQueue()
	{
		elements = (T[]) Array.newInstance(elements.getClass().getComponentType(), 100);
		size = 0;
	}
	
	/**
	 * Class constructor. Creates an array with the specified size
	 * 
	 * @param maxSize		the size of the array
	 */
	public PriorityQueue(int maxSize)
	{
		elements = (T[]) Array.newInstance(elements.getClass().getComponentType(), maxSize);
		size = 0;
	}
	
	/**
	 * Adds the given item to the heap using the addItem method after 
	 * checking the size of the heap and making room for the new item
	 * if necessary.
	 * 
	 * @param item		the item to be added to the heap
	 */
	public void insert(T item)
	{
		if (size < elements.length)
		{
			addItem(item);
		}
		else
		{
			T[] temp = (T[]) Array.newInstance(elements.getClass().getComponentType(), elements.length * 2);
			
			for (int i = 0; i < elements.length; i++)
				temp[i] = elements[i];
			
			elements = temp;
			
			addItem(item);
		}
	}
	
	/**
	 * Removes the minimum value in the heap. In this case the root.
	 * Aided by the newHole method. 
	 * 
	 * @return			the minimum value in the heap.
	 */
	public T deleteMin()
	{
		if (isEmpty())
			throw new MyException("The heap is empty");
		else
		{
			T returnValue = elements[0]; // the minimum/root value of the heap
			T item = elements[size - 1]; // the current last item in the heap.
			size --;
			
			int hole = 0; // current hole in the heap
			int newHole = newHole(hole, item); // new hole location in the heap
			
			while (newHole != -1)
			{
				elements[hole] = elements[newHole];
				hole = newHole;
				newHole = newHole(hole, item);
			}
			
			elements[hole] = item;
			return returnValue;
		}
	}
	
	/**
	 * Checks if the specified item is currently
	 * in the heap.
	 * 
	 * @param item		the item to find
	 * @return			true if the items exists, false otherwise
	 */
	public boolean contains(T item)
	{
		for (int i = 0; i < size; i++)
		{
			if (elements[i] == null)
				return false;
			else if (elements[i].equals(item))
				return true;
		}
		
		return false;
	}
	
	/**
	 * Deletes a specified item from the heap
	 * forcing a reordering of items in the heap.
	 * 
	 * @param item		
	 * @return		true if the item was deleted, false otherwise
	 */
    public boolean delete(T item)
    {
    	if(this.isEmpty()) //returns false if no elements in the heap
    		return false;
    	else if(size == 1)
    	{  // if there is only one element in the heap
    		if(elements[1].equals(item))
    		{
    			deleteMin();  // uses deleteMin() to remove the only element if it is
    			return true;  // equal to the element we're looking for
    		}else
    			return false;
    	}
    	else if(contains(item))
    	{  // if the size of the heap is > 1 and the element is in the heap
    		if(elements[1].equals(item))
    		{
    			deleteMin();  // deletes the first element if that element is the one we're
    			return true; 
    		}
    		else
    		{
	    		int location = find(item);  // location of the element in the heap array
		        int hole = location;  // placeholder that holds the location while percolating
		        
		        // percolates the element we were looking for up to the root position
		        for( ; hole > 1 ; hole /= 2 )
		        {
		        	T temp = elements[hole];  //saves the element previously in this location
		            elements[hole] = elements[hole / 2];
		            elements[hole/2] = temp;  // finishes the swap as the element is percolated up
		        }
		        deleteMin();  // deletes the element now that it is in the root position
		        			  // even though it is not really the 'min'
		        buildHeap();  //re-sorts elements of heap to ensure the Heap Ordering Property
		        return true;
    		}
    	}
    	return false;
    }
	
	/**
	 * Checks if the heap is empty and 
	 * returns the result
	 * 
	 * @return		true if empty, false otherwise
	 */
	public boolean isEmpty()
	{
		if (size() == 0)
			return true;
		else
			return false;
	}
	
	/**
	 * Returns the current size of the heap.
	 * 
	 * @return		the size of the heap
	 */
	public int size()
	{
		return size;
	}
	
	/**
	 * Prints the items in the heap in the order they're stored.
	 */
	public void print()
	{
		int i = 0; // the current location in the heap.
		System.out.println("Element List: ");
		
		while (i < size && elements[i] != null)
		{
			System.out.println(i+1 + ". " + elements[i]);
			i ++;
		}
	}
	
	/**
	 * Rebuilds the heap structure.
	 */
	private void buildHeap()
	{
		for( int i = size / 2; i > 0; i-- )
			percolateDown(i);
	 }
	
	/**
     * Internal method to percolate down in the heap.
     * 
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown(int hole)
    {
    	if (size > 0)
    	{
	        int child;
	        T tmp = elements[hole];
	
	        for ( ; hole * 2 <= size; hole = child )
	        {
	            child = hole * 2;
	            if (child != size && elements[child + 1].compareTo(elements[child]) < 0)
	                child++;
	            
	            if (elements[child].compareTo(tmp) < 0 )
	                elements[hole] = elements[child];
	            else			
	                break;
	        }
	        elements[hole] = tmp;
    	}
    }
	
	/**
	 * Adds the specified item to the heap in
	 * the correct postition.
	 * 
	 * @param item		the item to be added
	 */
	private void addItem(T item)
	{
		int hole = size; // the location of the new hole in the heap
		int parent = (hole - 1) / 2; // the location of the parent of the new hole
		
		while (hole != 0 && elements[parent].compareTo(item) > 0)
		{
			elements[hole] = elements[parent];
			hole = parent;
			parent = (hole - 1) / 2;
		}
		
		elements[hole] = item;
		size ++;
	}
	
	/**
	 * Aids in re-ordering the heap after a deletion by finding 
	 * where to place the new hole in the heap.
	 * 
	 * @param hole		the array index of the hole
	 * @param item		the item to be moved in the heap
	 * @return			the location of the hole in the heap
	 */
	private int newHole(int hole, T item)
	{
		int newHole = -1; // the new hole location in the heap.
		int smaller; // the location of the smaller child of the hole.
		
		if ((2 * hole + 1) <= size)
		{
			if (((2 * hole + 2) > size))
			{
				if (elements[2 * hole + 1].compareTo(item) < 0)
					newHole = 2 * hole + 1;
			}
			else
			{
				if (elements[2 * hole + 2].compareTo(elements[2 * hole + 1]) < 0)
					smaller = 2 * hole + 2;
				else
					smaller = 2 * hole + 1;
				
				if (elements[smaller].compareTo(item) < 0)
					newHole = smaller;
			}
		}
		
		return newHole;
	}
	
	/**
	 * Find the location in the heap 
	 * of the specified item.
	 * 
	 * @param item		the item to be found
	 * @return			the location in the heap of the item
	 */
	private int find(T item)
	{
		for (int i = 0; i < size; i++)
		{
			if (elements[i] == null)
				return -1;
			else if (elements[i].equals(item))
				return i;
		}
		
		return -1;
	}
	
}

